package org.cy.algorithm.chapter_04;

import org.cy.algorithm.util.AlgorithmUtil;

import java.util.Objects;

/**
 * 最大子序和
 */
public class MaxSubSum {

    /**
     * 分治法求解，暴力递归有难度。
     *
     * @param nums
     * @return
     */
    public static Result divideRecuse(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new Result();
        }
        Result result = divideRecuse(nums, 0, nums.length - 1);
        if (result.sum <= 0) {
            result = new Result();
        }
        return result;
    }

    /**
     * 分治法 递归
     *
     * @param nums
     * @return
     */
    public static Result divideRecuse(int[] nums, int left, int right) {
        if (left == right) {
            return new Result(left, left, nums[left]);
        }

        int mid = left + (right - left) / 2;
        Result leftResult = divideRecuse(nums, left, mid);
        Result rightResult = divideRecuse(nums, mid + 1, right);
        Result mergedMaxSubSum = mergeMaxSubSum(nums, left, mid, right);

        Result maxResult = leftResult.sum < rightResult.sum ? rightResult : leftResult;

        return maxResult.sum < mergedMaxSubSum.sum ? mergedMaxSubSum : maxResult;
    }

    private static Result mergeMaxSubSum(int[] nums, int left, int mid, int right) {
        int leftMaxSum = Integer.MIN_VALUE;
        int sum = 0;
        int leftMaxIndex = mid;

        for (int p1 = mid; p1 >= left ; p1--) {
            sum += nums[p1];
            if (sum > leftMaxSum) {
                leftMaxSum = sum;
                leftMaxIndex = p1;
            }
        }

        int rightMaxSum = Integer.MIN_VALUE;
        sum = 0;
        int rightMaxIndex = mid;
        for (int p2 = mid + 1; p2 <= right; p2++) {
            sum += nums[p2];
            if (sum > rightMaxSum) {
                rightMaxSum = sum;
                rightMaxIndex = p2;
            }
        }
        return new Result(leftMaxIndex, rightMaxIndex, leftMaxSum + rightMaxSum);
    }

    /**
     * 暴力法
     *
     * @param nums
     * @return
     */
    public static Result violent(int[] nums) {
        Result result = new Result();

        for (int i = 0; i < nums.length; i++) {
            int sum = nums[i];
            if (sum > 0 && sum > result.sum) {
                result.sum = sum;
                result.start = i;
                result.end = i;
            }
            for (int j = i + 1; j < nums.length; j++) {
                sum += nums[j];
                if (sum > 0 && sum > result.sum) {
                    result.sum = sum;
                    result.start = i;
                    result.end = j;
                }
            }
        }
        return result;
    }

    public static class Result {
        int start = -1;
        int end = -1;
        int sum = Integer.MIN_VALUE;

        public Result() {
        }

        public Result(int start, int end, int sum) {
            this.start = start;
            this.end = end;
            this.sum = sum;
        }

        @Override
        public boolean equals(Object o) {
            if (o == null || getClass() != o.getClass()) return false;
            Result result = (Result) o;
            return start == result.start && end == result.end && sum == result.sum;
        }

        @Override
        public int hashCode() {
            return Objects.hash(start, end, sum);
        }

        @Override
        public String toString() {
            return "Result{" +
                    "start=" + start +
                    ", end=" + end +
                    ", sum=" + sum +
                    '}';
        }
    }

    public static void main(String[] args) {
        for (int i = 0; i < 1000; i++) {
            int[] randomArray = AlgorithmUtil.createRandomArray(3);
            long begin = System.nanoTime();
            Result resultForEach = violent(AlgorithmUtil.copyArray(randomArray));
            System.out.println(String.format("暴力求解花费: %d (ns)", System.nanoTime() -begin));
            begin = System.nanoTime();
            Result divideRecuse = divideRecuse(AlgorithmUtil.copyArray(randomArray));
            System.out.println(String.format("递归求解花费: %d (ns)", System.nanoTime() -begin));
            if (divideRecuse.sum != resultForEach.sum) {
                AlgorithmUtil.printArray(randomArray);
                System.out.println(resultForEach);
                System.out.println(divideRecuse);
                System.out.println("Oops");
                return;
            }
        }
        System.out.println("OK");
    }
}
